<HTML>

<HEAD>
<TITLE>CS 440 Program 4</TITLE>
</HEAD>

<font size = 4>
<body bgcolor = "ffffff">

<CENTER><H2>CS 440
<BR>Program 4</H2></CENTER>

<H3><CENTER>due: November 11, 2011</CENTER></H3>

<H3>The Program</H3>

You will finish code generation for all of PAXI except for subprograms
(procedures), local variables, and parameters.  Your compiler will
generate programs having only one subprogram (main) with no local
variables and no procedure calls but otherwise will compile the entire
language.

<P>The pieces you will add for this program are the
<STRONG>writestr</STRONG> statement for quoted strings, Boolean
expressions, and control structures.  You will also add some code, a
loader, to your PVM interpreter (Program 1).

<H3>Boolean Expressions</H3>

Boolean expressions are described in productions 39 through 43 of the
PAXI Language Definition.  They involve the relational operators (= ,
< , <=, >, >=, and #) and Boolean operators (<STRONG>and</STRONG>,
<STRONG>or</STRONG>, <STRONG>not</STRONG>).

<P>A Boolean atom such as <TT>(var1 < var2)</TT> should leave a value
0 or 1 on the stack.  Each of <TT>var1</TT> and
<TT>var2</TT> in the above example will result in a value being left
on the stack (by arithmetic_expression).  You will generate code to
subtract these two values, test the result (perhaps using
<STRONG>blt</STRONG> in this example), and push either 0 or 1 onto the
stack.  The particular branching instruction used will depend on the
relational operator which appears in the Boolean atom.

<P>Boolean expressions (using operators <STRONG>and</STRONG>,
<STRONG>or</STRONG>, and <STRONG>not</STRONG>) are implemented in a manner
similar to arithmetic expressions.  Here you will leave integer values
on the stack as the values of Boolean expressions, Boolean terms, and
Boolean factors: 0 will be treated as <EM>false</EM> and 1 will be treated as
<EM>true</EM>.

<H3>Control Structures</H3>

The only control structures are <STRONG>if</STRONG>
... <STRONG>then</STRONG> ... <STRONG>else</STRONG>
... <STRONG>endif</STRONG>, <STRONG>while</STRONG>
... <STRONG>endwhile</STRONG>, and <STRONG>do</STRONG>
... <STRONG>endo</STRONG> which are described in productions 19
through 23 of the PAXI Language Definition.  Each of these control
structures involves evaluating a Boolean expression and transferring
control to a corresponding point in the program.  Transfer of control
is done with a branching instruction.

<P>Sometimes generating the branching instruction will involve
<EM>backpatching</EM>.  For example, implementing a while loop
involves a branch to the end (exit point) of the loop but the
instruction is generated before the location of the exit point is
known.  The problem is resolved by generating a blank instruction
(e.g. 0, 0, 0), noting its code store location, and writing this
instruction in its proper place after the body of the loop has been
generated.

<H3>The Writestr Statement</H3>

The only code generated for the <STRONG>writestr</STRONG> statement is
a PUTS instruction with the (data store) address of the
null-terminated string to be displayed.  In the case of a literal
string (second right hand side of production 32) you must allocate
memory for the string (literal strings will be stored consecutively in
the data store immediately following the variables and arrays).  When
the compiler writes its output it will first write a header (see
below), the instructions from the code store, and then write the
strings (as ASCII codes) to the output file.  For
<STRONG>writestr</STRONG> to display a string stored in an array
(third right hand side of production 32) you must get the argument for
the PUTS instruction from the symbol table entry for the array.

<H3>The Header and the Loader</H3>

A further change in this program is that a four-integer
<EM>header</EM> must now begin the compiler's output file.  The first
integer is the size of the code store, i.e. the number of integers in
the PVM file which will be loaded into the code store array.  The
second is the position in the data store where the strings will begin
(the first data store location <EM>past</EM> the space allocated for
variables and arrays).  The third is the amount of data store used for
strings.  The fourth is the program entry point (the code store
address of main) -- for Program 4 this will be 0.

<P>The <EM>loader</EM> is a piece of code added to the PVM
interpreter.  It will read the header and use the information it finds
there to allocate memory for the code store and data store, place the
instructions into the code store, the strings into the data store, and
prepare to start interpreter execution at the program's entry point.

<H3>To Hand In</H3>

You will hand in a source listing and a sample terminal session.  The
source listing should include your yacc file and any relevant source
files (you need not turn in your lex file or additions to Program 1).
Sample data will be supplied later.

</HTML>